package org.leetcode.middle.leetcode79;

public class Solution {
    public boolean exist(char[][] board, String word) {

        int n =board.length;
        int w = board[0].length;

        boolean [][] visited = new boolean[n][w];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board,visited,i,j,word,0);
                if (flag){
                    return true;
                }
            }
        }

        return false;
    }


    private boolean check(char[][] board, boolean[][] visited, int i, int j, String word, int k){
        if (board[i][j]!=word.charAt(k)){
            return false;
        }else if (k==word.length()-1){
            return true;
        }
        int [][] directions ={{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        boolean result = false;

        visited[i][j]=true;

        for (int [] dir:directions) {
            int newI=i+dir[0];
            int newJ=j+dir[1];

            if (newI>=0 && newJ>=0 && newI<board.length && newJ<board[0].length){
                if (!visited[newI][newJ]){
                    boolean check = check(board, visited, newI, newJ, word, k + 1);
                    if (check){
                        result=true;
                        break;
                    }
                }
            }
        }

        visited[i][j]=false;
        return result;

    }


    private boolean backtracking(char [][] board,String word,StringBuilder str){

        if (str.length()==word.length()){
            if (str.toString()==word){
                return true;
            }else {
                return false;
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                str.append(board[i][j]);
                backtracking(board,word,str);

                str.deleteCharAt(str.length()-1);
            }
        }


        return true;

    }
}
